\documentclass{article}[11pt]
\usepackage{amssymb,amsmath,xspace}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[french]{babel}
\usepackage[mathscr]{eucal}
\usepackage{color}
\usepackage{a4wide,color}
\usepackage{ifpdf}
\usepackage{enumitem} % puce magique :) 
\usepackage{pifont} % puce magique :) 

\usepackage[ruled,vlined,french]{algorithm2e}


\usepackage{tikz}
\usepackage{tkz-berge}
\PassOptionsToPackage{pdftex}{graphicx}
\usetikzlibrary{arrows,shapes}



%% Doc des graph: http://graphtheoryinlatex.blogspot.com/
%% https://docs.google.com/viewer?url=http%3A%2F%2Faltermundus.fr%2Fpages%2Fdownloads%2FTKZdoc-graph.pdf
%% doc des algo  https://docs.google.com/viewer?url=http%3A%2F%2Fwww.lirmm.fr%2F~fiorio%2FAlgorithmSty%2Falgorithm2e.pdf
%% http://altermundus.fr/pages/downloads/

\ifpdf
  \usepackage[pdftex]{graphicx}
  \usepackage[pdftex,pagebackref]{hyperref}
  \def\EXTFIG{pdf_t}
\else
  \usepackage[dvips]{epsfig}
  \usepackage[pagebackref]{hyperref}
  \def\EXTFIG{pstex_t}
\fi

\def\inputfig#1#2{\scalebox{#1}{\input{#2.\EXTFIG}}}
\def\inputfigc#1#2{\begin{center}\inputfig{#1}{#2}\end{center}}

\sloppy
\setlength{\parskip}{.5ex}
\pagestyle{empty}

\def\cyril#1{\textcolor{blue}{[Cyril: #1]}}
\def\leq{\leqslant}\def\le{\leqslant}
\def\geq{\geqslant}\def\ge{\geqslant}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\pare}[1]{\left({#1}\right)}
\newcommand{\set}[1]{\left\{{#1}\right\}}
\newcommand{\ang}[1]{\left\langle {#1} \right\rangle}
\newcommand{\range}[2]{\set{{#1},\dots,{#2}}}
\def\beginsmall#1{\vspace{-\parskip}\begin{#1}\itemsep-\parskip}
\def\endsmall#1{\end{#1}\vspace{-\parskip}}

\newcounter{question}
\def\Q{%
\medskip\medskip
\addtocounter{question}{1}%
\medskip\noindent\textbf{\textcolor{red}{Question \thequestion.~}}}

\newcounter{reponse}
\def\R{%
\medskip\medskip
\addtocounter{reponse}{1}%
\medskip\noindent\textbf{\textcolor{cyan}{Réponse \thequestion.~}}}


\begin{document}

\medskip
\hrule
\medskip
\noindent{\textsc{\LARGE \textcolor{cyan}{N}ahelou \textcolor{cyan}{S}ébastien}}\\
\textcolor{cyan}{M}aster Réseaux et Systèmes Mobiles\\
\textcolor{cyan}{N}uméro étudiant: 607013\\
\hrule
\medskip
\medskip

\noindent{\textsc{\LARGE Algorithmes Distribués}}\\[3ex]
\noindent{\textsc{\Large Master2 Informatique}}\\[2ex]
\noindent{Novembre 2011}

\medskip
\medskip

\hrule
\medskip

\textit{Ce devoir est à rendre par courriel à
  \textsl{gavoille@labri.fr} au plus tard \textbf{lundi 19 décembre
    2011} minuit. Il doit se présenter sous la forme d'un fichier de
  quelques pages au format .pdf ou .ps comprenant vos nom, prénom et
  spécialité de Master. Répondez de manière concise tout en justifiant
  vos réponses. La notation tiendra compte, en premier lieu, de
  l'argumentation de vos réponses.}

\medskip
\hrule

\Q Expliquer pourquoi, éventuellement en donnant un exemple, un
algorithme distribué déterministe peut avoir plusieurs exécutions
différentes, et donc fournir des résultats différents, sur le même
graphe et avec les mêmes entrées.

\R Pour les systèmes distribués, nous rencontrons plusieurs contraintes:
\begin{itemize}
\item Vitesse de transmition des messages
\item Fiabilité: problèmes matériels, réseaux ou logiciels
\item Communications non fiables
\item ...
\end{itemize}
De ce fait, il est impossible de prévoir l'ordre des évenements, ce qui peux entrainer des résultats différent pour plusieurs exécutions.\\

Voici un exemple qui récupère la couleur du voisin le plus lent:\\
\begin{algorithm}[H]
\SetLine
\Deb{
\PourCh{voisins}{Envoyer(ma couleur)}
\Pour{i allant de 1 à nbVoisin}{$couleur \longleftarrow Recevoir()$}
}
\caption{Réception de la dernière couleur}
\end{algorithm}

\medskip
\medskip

Un ensemble de sommets $S$ d'un graphe $G$ est dit
\textit{indépendant} s'il n'y a pas d'arête de $G$ entre deux sommets
quelconques de $S$. Un ensemble indépendant $S$ est \emph{maximal} si
dans $G$ il n'existe pas d'ensemble indépendant $S'$ contenant
strictement $S$, c'est-à-dire tel que $S \subset S'$ et $S \neq S'$.

\Q Donner un exemple de graphe ayant un ensemble indépendant maximal
$S$ et qui possède pourtant un ensemble indépendant $S'$ de taille
strictement plus grande que celle de $S$.

\R
\begin{center}
\begin{tikzpicture}
 \tikzstyle{VertexStyle}=[shape=circle,fill=blue!30,text= black,draw]
 \Vertex[x=0,y=0]{A}
 \Vertex[x=4,y=0]{C}
 \tikzstyle{VertexStyle}=[shape=circle,fill=orange,text= black,draw]
 \Vertex[x=2,y=0]{B}
 \Edges(A,B,C)
 \end{tikzpicture}
\end{center}

\begin{itemize}
\item Soit S1 l'ensemble indépendant maximal formé par les sommets A et C: Card(S1)=2.
\item Soit S2 l'ensemble indépendant maximal formé par le sommet B: Card(S2)=1.
\end{itemize}
On a donc:
 card(S1) > card(S2)

\medskip
\medskip

On rappelle qu'une $k$-coloration pour $G$ est une fonction $c: V(G)
\to \range{1}{k}$ telle que $c(u) \neq c(v)$ si $u$ et $v$ sont
voisins. Pour une coloration $c$ de $G$, on note $I_i$ l'ensemble des
sommets de couleur $i$. Plus formellement $I_i = \set{ u \in V(G):
  c(u) = i}$.

\Q Pour le graphe dessiné ci-dessous, donner une $3$-coloration $c$
telle qu'aucun des ensembles $I_1$, $I_2$, $I_3$ ne soit un ensemble
indépendant maximal pour $G$.

\inputfigc{1}{nov2011-fig1}

\R 

\begin{center}
\begin{tikzpicture}
 \tikzstyle{VertexStyle}=[shape=circle,fill=blue!30,text= black,draw]
 \Vertex[x=0,y=4]{A}
 \Vertex[x=2,y=2]{D}
 \Vertex[x=4,y=0]{H}
 \tikzstyle{VertexStyle}=[shape=circle,fill=orange,text= black,draw]
 \Vertex[x=2,y=4]{B}
 \Vertex[x=0,y=2]{C}
 \Vertex[x=2,y=0]{G}
 \tikzstyle{VertexStyle}=[shape=circle,fill=yellow,text= black,draw]
 \Vertex[x=4,y=2]{E}
 \Vertex[x=0,y=0]{F}
 \Edges(F,G,H)
 \Edges(C,D,E)
 \Edges(A,B)
 \Edges(A,C,F)
 \Edges(B,D,G)
 \Edges(E,H)
 \end{tikzpicture}
\end{center}


\Q Démontrer que si $G$ est un graphe connexe possédant une
$2$-coloration $c$, alors les ensembles $I_1$ et $I_2$ sont tout deux
des ensembles indépendant maximaux pour $G$.

\R Raisonnement par l'absurde: \\
Supposons que $I_{1}$ ne soit pas un ensemble indépendant maximal alors il existe un sommet $U$ tel que $U$ n'est pas voisin d'un sommet de $I_{1}$.\\
Le graphe $G$ étant connexe et 2-coloriable, on en déduit que $U$ est relié à un sommet de $I_{2}$.\\
L'ensemble $I_{2}$ étant indépendant maximal, le sommet $U$ ne peut-être relié à un sommet de $I_{2}$.\\
Le sommet $U$ n'appartient ni à $I_{1}$ ni à $I_{2}$, ce qui est impossible.\\

\Q Rappeler les caractéristiques du modèle LOCAL.

\R Caractéristiques du modèle LOCAL:
\begin{itemize}
\item [\ding{43}] Identité unique
\item [\ding{43}] Mode synchrone
\item [\ding{43}] Pas de taille de messages
\item [\ding{43}] Pas d'erreur
\item [\ding{43}] Calculs locaux gratuits
\end{itemize}

\medskip
\medskip

Tous les algorithmes distribués que l'on considèrera dans la suite
seront dans le modèle LOCAL. On se donne un graphe $G$ avec $n$
sommets. On suppose que les sommets de $G$ possède une $k$-coloration,
et que pour chaque sommet $u$, $k$ et la couleur $c(u)$ sont connues
de $u$.

\Q Donner un algorithme distribué permettant de calculer un ensemble
indépendant maximal pour $G$. Analyser sa complexité en temps.

L'ensemble $S$ calculé par votre algorithme sera représenté par une
variable locale $s$ indiquant pour chaque sommet s'il est dans $S$ ou
pas. Plus précisément, pour chaque sommet $u$, $s(u) \in \set{0,1}$ et
$s(u)=1$ si et seulement si $u \in S$.


\R Algorithme de Luby:

\begin{enumerate}
\item Chaque sommet tire un nombre aléatoire.
\item Chaque sommet envoie ce nombre à ces voisins.
\item Le sommet est élu si son entier est plus grand que celui de ses voisins.
\item Pour avoir un ensemble maximal, on recommence tant que l'algorithme n'est pas stabilisé.
\end{enumerate}

\begin{algorithm}[H]
\SetLine
\emph{Initialisation :}\\
\Deb{
$ s \leftarrow faux$\\
$ voisinElu \leftarrow faux$\\
}

\emph{\\Réception :}\\
\Deb{
NewPulse\\
$ myID \leftarrow rand()$\\
\lPourCh{voisins}{Envoyer({myID,s})}

\PourCh{voisins}{
	$vID,vS \leftarrow Recevoir()$\\
	\Si{!voisinElu || s}{
		\Si{$myID > vID$}{
			$s \leftarrow vrai$\\
			\lPourCh{voisins}{Envoyer({vrai})}			
			}
			\lPourCh{voisins}{Envoyer({faux})}\\	
			\lPourCh{voisins}{
			$voisinElu \leftarrow  Recevoir()$			
			}
	}
}
}
\caption{Détermination d'un ensemble indépendant}
\end{algorithm}


\paragraph{Complexité:} A chaque tirage d'entier (ie chaque round), le nombre d'arrêtes qui disparaît vaut la moitié du nombre d'arrête active.
Soit une complexité en temps de O(log n).


\medskip
\medskip

Un ensemble $M$ de sommets de $G$ est \emph{$r$-dominant} si pour tout
sommet $u$ de $G$, il existe un sommet $v \in M$ à distance au plus
$r$ de $u$. On rappelle que la distance entre deux sommets d'un graphe
est le plus petit nombre d'arête d'un chemin connectant $u$ et $v$. Un
ensemble dominant est simplement un ensemble $r$-dominant pour
$r=1$. Il n'est pas difficile de voir que tout ensemble indépendant
maximal est aussi un ensemble dominant.

\Q Déduire des questions précédantes que tout arbre à $n$ sommets
possède un ensemble indépendant maximal de taille au moins $n/2$ et un
ensemble dominant de taille au plus $n/2$.

\R On sait qu'un arbre est 2-coloriable. En effet il suffit de choisir la couleur en fonction de l'étage.
La racine prends la couleur C1, ses fils prennent la couleur C2 etc...
Or d'après la question 4, tous graphe 2-coloriable possèdent 2 ensembles indépendant maximaux. Donc l'un de ces ensembles a une taille >= n/2.

De plus si $I_1$ >= n/2 alors $I_2$ < n/2 car G = $I_1$ U $I_2$.\\
 Comme $I_2$ est un ensemble indépendant maximal (donc dominant) on a bien :

\begin{itemize}
\item $I_1$ >= n/2 est un ensemble indépendant.
\item $I_2$ < n/2 est un ensemble dominant.
\end{itemize}
et inversement.


\Q Donner un exemple ayant toutes les trois propriétés suivantes:
\beginsmall{enumerate}
\item il possède un ensemble dominant $M$ de taille $|M| \ge 3$,
\item il ne possède pas d'ensemble dominant de taille $<|M|$,
\item $M$ n'est pas un ensemble indépendant maximal.
\endsmall{enumerate}

\R 

\begin{center}
\begin{tikzpicture}
 \tikzstyle{VertexStyle}=[shape=circle,fill=blue!0,text= black,draw]
 \Vertex[x=0,y=0]{A}
 \tikzstyle{VertexStyle}=[shape=circle,fill=blue!30,text= black,draw]
 \Vertex[x=1,y=0]{B}
 \Vertex[x=2,y=0]{C}
 \tikzstyle{VertexStyle}=[shape=circle,fill=blue!0,text= black,draw]
 \Vertex[x=3,y=0]{D}
 \Vertex[x=4,y=0]{E}  
 \tikzstyle{VertexStyle}=[shape=circle,fill=blue!30,text= black,draw]
 \Vertex[x=5,y=0]{F}
 \Edges(A,B,C,D,E,F)
 \end{tikzpicture}
\end{center}




\Q Démontrer que tout ensemble $3$-dominant $M$ pour l'arbre à $n$
sommets dessiné ci-dessous, un peigne à $b = n/4$ branches avec $b \in
\mathbb{N}^*$, est de taille $|M| \ge n/4$.

\inputfigc{1}{nov2011-fig2}

\R Raisonnement par récurrence:
Soit G(k) le peigne possédant k branches.

\'Etape 0:\\
 Pour 1 branche, on a 4 sommets or il faut minimum 1 sommet dans M donc $|M| \ge n/4$.\\

 \'Etape k:\\
 Pour k branches, on a k*4 sommets. On suppose que $|M| \ge n/4$\\

\'Etape k+1:\\
On observe qu'il n'y à pas de sommet de G(k) à distance $ \leq 3$ du sommet numéro 4 de G(k+1). Si aucun sommet de la branche k+1 n'est dans M alors le G(k) n'est plus 3-dominant.
Comme la distance entre n'importe quel sommet de la branche k+1 est à distance $ \leq 4$ d'un sommet de G(k), il suffit d'ajouter un sommet de la branche k+1 à M pour rendre G(k+1) 3-dominant. \\

\begin{center}
\begin{tikzpicture}

 \SetVertexLabelOut
\tikzstyle{VertexStyle}= [
			shape = circle,
			minimum size = 10pt,
			draw]

 \Vertex[x=0,y=0,Lpos=90]{0}
 \SetVertexNoLabel
  \Vertex[x=0,y=-1,]{B}
  \Vertex[x=0,y=-2]{C}
  \Vertex[x=0,y=-3]{D}
 \Edges(0,B,C,D)
     \SetVertexLabel
  \Vertex[x=1,y=0,Lpos=90]{1}
   \SetVertexNoLabel
  \Vertex[x=1,y=-1]{B}
  \Vertex[x=1,y=-2]{C}
  \Vertex[x=1,y=-3]{D}
 \Edges(1,B,C,D)
   
 
   
   
  \Vertex[x=3,y=0]{A8}
  \Vertex[x=3,y=-1]{B}
  \Vertex[x=3,y=-2]{C}
  \Vertex[x=3,y=-3]{D}
 \Edges(A8,B,C,D)
 
 
 %% Rang K  
    \SetVertexLabel
     \tikzstyle{VertexStyle}=[shape=circle,fill=orange,text= black,draw]
   \Vertex[x=5,y=0,Lpos=90]{k}
     \tikzstyle{VertexStyle}=[shape=circle,fill=white,text= black,draw]
    \SetVertexNoLabel
  \Vertex[x=5,y=-1]{B}
  \Vertex[x=5,y=-2]{C}
  \Vertex[x=5,y=-3]{D}
 \Edges(k,B,C,D)
 
 %% rang K+1
     \SetVertexLabel
  \Vertex[x=6,y=0,Lpos=90]{k+1}
      \SetVertexNoLabel
  \Vertex[x=6,y=-1]{B}
  \Vertex[x=6,y=-2]{C}
   \tikzstyle{VertexStyle}=[shape=circle,fill=orange,text= black,draw]
  \Vertex[x=6,y=-3]{D}
 \Edges(k+1,B,C,D)
 
 
  \Edges(0,1)
  \SetUpEdge[lw=1.5pt]
  \SetUpEdge[style=dashed]
  \Edges(1,A8)
  \Edges(A8,k)  
  \SetUpEdge[lw=1pt]
  \Edges(k,k+1)

 \end{tikzpicture}
\end{center}

\medskip
\medskip\medskip\medskip\medskip

On supposera connu un algorithme distribué \textsc{SmallDom} calculant
pour tout arbre à $n$ sommets un ensemble dominant $M$ d'au plus $n/2$
sommets et ceci en temps $f(n)$. On supposera que \textsc{SmallDom}
renvoie en sortie pour chaque sommet $u$ une variable $m(u) \in
\set{0,1}$ telle que $m(u)=1$ si et seulement si $u \in M$.

On veut concevoir un algorithme distribué \textsc{SmallDom2}
permettant de construire un <<~petit~>> ensemble $3$-dominant ou
$4$-dominant pour tout arbre à $n$ sommets. L'idée est d'appliquer
deux fois la procédure \textsc{SmallDom}. Dans la suite un
\emph{cluster} est un sous-graphe connexe, ici un sous-arbre.

Plus précisément on réalise les quatres étapes suivantes, chacune
illustrée sur la figure ci-dessous~:

\noindent Algorithme \textsc{SmallDom2}~:

\beginsmall{enumerate}
\item[(1)] Construire un ensemble dominant $M$ avec \textsc{SmallDom}
  (sommets en bleu).
\item[(2)] Partitionner les sommets en clusters en fonction de $M$ (voir
  détails ci-après).
\item[(3)] Construire un ensemble dominant $M'$ (en vert) pour l'arbre
  des clusters avec \textsc{SmallDom}.
\item[(4)] Le résultat est $M'' = \set{ x \in M \cap C \mid C \in M'}$
  (en rouge), les sommets de $M$ appartenant à un cluster de $M'$.
\endsmall{enumerate}

\inputfigc{1}{nov2011-fig3}

En plus de former un sous-arbre et une partition des sommets, chaque
cluster doit vérifier les deux propriétés suivantes~: (P1) Il y a
exactement un sommet de $M$ par cluster. (P2) Dans un cluster $C$,
tout sommet $u \notin M$ doit être voisin de l'unique sommet $x \in M
\cap C$.

L'arbre des clusters utilisé à l'étape (3) est obtenu en contractant
toutes les arêtes internes des clusters formés à l'étape (2).

\Q Donner un algorithme distribué permettant de construire de tels
clusters à partir d'un ensemble dominant $M$ donné par la variable
$m$. Plus précisément, la sortie de l'algorithme sera, pour chaque
sommet $u$, une variable $c(u)$ indiquant le nom du sommet de $M$ du
cluster de $u$. Dit autrement, si $C$ est un cluster et si $x$ est
l'unique sommet de $M \cap C$, alors on doit avoir $c(u) = x$ pour
tout $u \in C$.

\medskip

\begin{algorithm}[H]
\SetLine
\emph{\\Réception :}\\
\Deb{
NewPulse\\
\lPourCh{voisins}{Envoyer({m,v});}\\
\eSi{m = 1}{c$\leftarrow$id}{
	\PourCh{voisins v}{
		m $\leftarrow$ Recevoir(v);\\
		\Si{m = 1}{c$\leftarrow$v}	
	
	}
}
}
\caption{Cluster}
\end{algorithm}



\Q Montrer que \textsc{SmallDom2} calcule un ensemble $M''$ qui est
$r$-dominant avec $r\le 4$. Est-ce que <<~$4$~>> est la meilleure
borne possible pour $r$~?

Si oui, démontrer que pour tout arbre et toute exécution de
\textsc{SmallDom2} on a bien $r \le 3$. Sinon, donner un
contre-exemple $M''$ où $r\ge 4$, c'est-à-dire l'exemple d'un arbre à
$n$ sommets avec un ensemble dominant $M$ de taille $|M|\le n/2$ où la
stratégie adoptée par \textsc{SmallDom2} donnera un sommet à
distance~$4$ de tout sommet de~$M''$.

\R 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% A FAIRE  !!!!!!!!!!!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\Q Montrer que l'ensemble construit par \textsc{SmallDom2} est de
taille au plus $n/4$.

\R On sait que SMALLDOM calcule pour tout arbre à $n$ sommets un ensemble dominant $M$ d'au plus $n/2$ sommets. Or SMALLDOM2 ré-utilise SMALLDOM sur $M$ donc il calcule un ensemble d'au plus  $(n/2)/2$ soit $n/4$.


\Q Donner le pseudo-code pour \textsc{SmallDom2}, puis exprimer en
fonction de $f$ sa complexité en temps.

\R 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% A FAIRE  !!!!!!!!!!!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\vfill\hfill{\bf FIN.}
\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
